#include "ipgui_triangle_ras.h"

/* 三角形的光栅化采用的像素点模型是连续方块模型，而tile采用的是离散点模型，
 * 因此在进行三角形光栅化时，需要将连续方块模型转换为离散点模型，或将离散点模型转化为连续方块模型
 * 这里采取的办法是将tile离散点模型转化为连续方块模型进行计算，转换方法是将右下的点坐标x和y分别加上1
 */

#define ipgui_make_scoord(i,f) (((i) << IPGUI_PIXEL_BITS) | (f)) /* f must be 0 ~ 2^IPGUI_PIXEL_BITS - 1 */
#define ipgui_scoord_down(scoord)  ((scoord) & ((~0U) << IPGUI_PIXEL_BITS))
#define ipgui_scoord_up(scoord)     ((scoord) + ((1 << IPGUI_PIXEL_BITS) - 1) & ((~0U) << IPGUI_PIXEL_BITS))

__IPGUI_STATIC__ void ipgui_scanline_ras(ipgui_coord_t scan_y, 
                                            ipgui_scoord_t x1, ipgui_scoord_t x2, 
                                            ipgui_scoord_t x3, ipgui_scoord_t x4,
                                            ipgui_triangle_ras_attr_t * attr, ipgui_aabb_t * clip,
                                            ipgui_tile_t * tile);

__IPGUI_STATIC__ void ipgui_sort3p_by_y(ipgui_point_t * p1, ipgui_point_t * p2, 
                                            ipgui_point_t * p3, ipgui_point_t ** sort_arr);

/* p1 p2 p3是连续方块模型，在这个模型中，0,0到800,400才能表示整个屏幕（假设屏幕尺寸是800*480）
 * 而tile是离散点模型，在这个模型中，0,0到799,479就能表示整个屏幕（假设屏幕尺寸是800*480）
 * 因此需要将连续方块模型转换为离散点模型 
 */
__IPGUI_API__ void ipgui_triangle_ras(
        ipgui_point_t * p1, ipgui_point_t * p2, ipgui_point_t * p3, 
        ipgui_triangle_ras_attr_t * attr, ipgui_tile_t * tile)
{
    ipgui_coord_t y_min, y_mid, y_max;
    ipgui_coord_t x_at_ymin, x_at_ymid, x_at_ymax;
    ipgui_coord_t y_min_scan, y_max_scan;
    ipgui_aabb_t buffer, self, draw;
    ipgui_point_t * sort_arr[3];

    buffer = ipgui_tile_aabb_gen(tile);
    buffer.end.x += 1; /* 转换为连续方块模型 */
    buffer.end.y += 1; /* 转换为连续方块模型 */
    self.end.x = self.start.x = p1->x;
    self.end.y = self.start.y = p1->y;
    ipgui_aabb_update_with_point(&self, p2);
    ipgui_aabb_update_with_point(&self, p3);
    if (0 != ipgui_rect_2d_intersect(&draw, &buffer, &self))
        return;

    /* 连续方块模型的边界也不能重合 */
    if (draw.end.x == draw.start.x || draw.end.y == draw.start.y)
        return;

    ipgui_sort3p_by_y(p1, p2, p3, sort_arr);/* 将点按y从小到大排序，第一个点为y值（屏幕靠上）最小的点 */

    y_min = sort_arr[0]->y;
    y_mid = sort_arr[1]->y;
    y_max = sort_arr[2]->y;
    x_at_ymin = sort_arr[0]->x;
    x_at_ymid = sort_arr[1]->x;
    x_at_ymax = sort_arr[2]->x;

    ipgui_coord_t y_scan;
    ipgui_coord_t y_scan_next;
    ipgui_scoord_t x1, x2, x3, x4;
    int y_cum;

    /* 光栅化上三角形 */
    if (y_mid > y_min) { /* 判断上三角形是否存在 */
        y_min_scan = y_min;
        y_max_scan = y_mid;

        /* 扫描线y跨度是否与draw包围盒y跨度有交集 */
        if (!(y_max_scan <= draw.start.y || y_min_scan >= draw.end.y)) {
            if (y_max_scan > draw.end.y) y_max_scan = draw.end.y; /* clip y */
            if (y_min_scan < draw.start.y) y_min_scan = draw.start.y; /* clip y */

            y_max_scan -= 1;
            
            /* 最高点和最低点的像素差 */
            int dy1 = (y_max - y_min) << IPGUI_PIXEL_BITS;
            int dx1 = (x_at_ymax - x_at_ymin) << IPGUI_PIXEL_BITS;
            /* 中间点和最高点的像素差 */
            int dy2 = (y_mid - y_min) << IPGUI_PIXEL_BITS;
            int dx2 = (x_at_ymid - x_at_ymin) << IPGUI_PIXEL_BITS;

            y_cum = IPGUI_PIXEL_PRECI * (y_min_scan - y_min);
            x3 = (x_at_ymin << IPGUI_PIXEL_BITS) + y_cum * dx1 / dy1;
            x4 = (x_at_ymin << IPGUI_PIXEL_BITS) + y_cum * dx2 / dy2;
            if (x3 > x4) {
                int temp;
                temp = x3;
                x3 = x4;
                x4 = temp;
            }
            y_cum += IPGUI_PIXEL_PRECI;
            for(y_scan = y_min_scan;
                y_scan <= y_max_scan; y_scan ++)
            {
                x1 = (x_at_ymin << IPGUI_PIXEL_BITS) + y_cum * dx1 / dy1;
                x2 = (x_at_ymin << IPGUI_PIXEL_BITS) + y_cum * dx2 / dy2;

                if (x1 > x2) {
                    int temp;
                    temp = x1;
                    x1 = x2;
                    x2 = temp;
                }

                /* 光栅化扫描线 */
                ipgui_scanline_ras(y_scan, x1, x2, x3, x4, attr, &draw, tile);
                y_cum += IPGUI_PIXEL_PRECI;
                x3 = x1;
                x4 = x2;
            }
        }
    }

    /* 光栅化下三角形 */
    if (y_mid < y_max) { /* 判断下三角形是否存在 */
        y_min_scan = y_mid;
        y_max_scan = y_max;

        /* 扫描线y跨度是否与draw包围盒y跨度有交集 */
        if (!(y_max_scan <= draw.start.y || y_min_scan >= draw.end.y)) {
            if (y_max_scan > draw.end.y) y_max_scan = draw.end.y; /* clip y */
            if (y_min_scan < draw.start.y) y_min_scan = draw.start.y; /* clip y */

            y_min_scan += 1;

            /* 最高点和最低点的像素差 */
            int dy1 = (y_min - y_max) << IPGUI_PIXEL_BITS;
            int dx1 = (x_at_ymin - x_at_ymax) << IPGUI_PIXEL_BITS;
            /* 中间点和最低点的像素差 */
            int dy2 = (y_mid - y_max) << IPGUI_PIXEL_BITS;
            int dx2 = (x_at_ymid - x_at_ymax) << IPGUI_PIXEL_BITS;

            y_cum = -IPGUI_PIXEL_PRECI * (y_max - y_max_scan);
            x1 = (x_at_ymax << IPGUI_PIXEL_BITS) + y_cum * dx1 / dy1;
            x2 = (x_at_ymax << IPGUI_PIXEL_BITS) + y_cum * dx2 / dy2;
            if (x1 > x2) {
                int temp;
                temp = x1;
                x1 = x2;
                x2 = temp;
            }
            y_cum -= IPGUI_PIXEL_PRECI;
            for(y_scan = y_max_scan;
                y_scan >= y_min_scan; y_scan = y_scan_next)
            {
                y_scan_next = y_scan - 1;

                /* 计算当前扫描线的x坐标 */
                /*      P2
                ---------●------
                        /|
                       / |              
                      /  |              P2.x = P1.x + Δy * (1 / k) 
                     /   | 
                ----●-----------
                    P1           
                */
                x3 = (x_at_ymax << IPGUI_PIXEL_BITS) + y_cum * dx1 / dy1;
                x4 = (x_at_ymax << IPGUI_PIXEL_BITS) + y_cum * dx2 / dy2;

                if (x3 > x4) {
                    int temp;
                    temp = x3;
                    x3 = x4;
                    x4 = temp;
                }

                /* 光栅化扫描线 */
                ipgui_scanline_ras(y_scan_next, x1, x2, x3, x4, attr, &draw, tile);
                y_cum -= IPGUI_PIXEL_PRECI;
                x1 = x3;
                x2 = x4;
            }
        }
    }
}

/* 根据y值从小到大对三点进行排序 */
__IPGUI_STATIC__ void
ipgui_sort3p_by_y(ipgui_point_t * p1, ipgui_point_t * p2, 
    ipgui_point_t * p3, ipgui_point_t ** sort_arr)
{
    if (p1->y <= p2->y && p1->y <= p3->y) {
        sort_arr[0] = p1;
        if (p2->y <= p3->y) {
            sort_arr[1] = p2;
            sort_arr[2] = p3;
        } else {
            sort_arr[1] = p3;
            sort_arr[2] = p2;
        }
    } else if (p2->y <= p1->y && p2->y <= p3->y) {
        sort_arr[0] = p2;
        if (p1->y <= p3->y) {
            sort_arr[1] = p1;
            sort_arr[2] = p3;
        } else {
            sort_arr[1] = p3;
            sort_arr[2] = p1;
        }
    } else {
        sort_arr[0] = p3;
        if (p1->y <= p2->y) {
            sort_arr[1] = p1;
            sort_arr[2] = p2;
        } else {
            sort_arr[1] = p2;
            sort_arr[2] = p1;
        }
    }
}

__IPGUI_STATIC__ void gen_axis_distance(ipgui_scoord_t from, 
                                    ipgui_scoord_t to, 
                                    int * dist)
{
    ipgui_coord_t min_up, max_up;
    unsigned int min_fract, max_fract;

    if (to > from) {
        min_up = ipgui_scoord_up(from);
        min_fract = min_up - from;
        max_up = ipgui_scoord_up(to);
        max_fract = max_up - to;

        * dist = max_up - min_up - max_fract + min_fract;
    } else {
        min_up = ipgui_scoord_up(to);
        min_fract = min_up - to;
        max_up = ipgui_scoord_up(from);
        max_fract = max_up - from;

        * dist = -(max_up - min_up - max_fract + min_fract);
    }
}

/* 斜率存在返回1，斜率不存在返回0 */
__IPGUI_STATIC__ __IPGUI_INLINE__ int line_slope_exist(ipgui_line_t * line)
{
    return !(line->end.x == line->start.x);
}

/* 同号返回1，异号返回0 */
__IPGUI_STATIC__ __IPGUI_INLINE__ int same_sign(int a, int b) 
{
    return (a ^ b) >= 0;
}

/* 直线已经和aabb相交了, 直线的斜率必须存在 */
__IPGUI_STATIC__ int gen_trim_area_size(ipgui_line_t * line, ipgui_aabb_t * aabb, int up_down)
{
    if (!line_slope_exist(line))
        return -1;

    unsigned int up_area;
    ipgui_coord_t dx = line->end.x - line->start.x;
    ipgui_coord_t dy = line->end.y - line->start.y;
    ipgui_coord_t aabb_w = aabb->end.x - aabb->start.x + 1;
    ipgui_coord_t aabb_h = aabb->end.y - aabb->start.y + 1;

    up_area = 0;
    if ((line->start.y == line->end.y) && ((IPGUI_ABS(line->end.x- line->start.x)) + 1)) {/* 给ipgui_aabb_clip_line_cohen打的补丁，比如裁剪会出现这种情况line->start.x = 62, line->start.y = 63, line->end.x = 63, aabb->end.y = 63 */
        if (line->start.y == aabb->start.y) up_area = 0;
        else if (line->start.y == aabb->end.y) up_area = IPGUI_PIXEL_AREA;
    }
    else if (same_sign(dx, dy)) {
        if ((aabb_h - 1) == IPGUI_ABS(dy)) {
            up_area = (((aabb->end.x << 1) - line->start.x - line->end.x) * aabb_h) >> 1;
        } else if ((aabb_w - 1) == IPGUI_ABS(dx)) {
            up_area = ((line->start.y + line->end.y - (aabb->start.y << 1)) * aabb_w) >> 1;
        } else if ((line->start.x == aabb->start.x) || (line->end.x == aabb->start.x)) {
            if (line->start.x == aabb->start.x) {
                up_area = IPGUI_PIXEL_AREA - (((aabb->end.y - line->start.y) * (line->end.x - aabb->start.x)) >> 1);
            } else {
                up_area = IPGUI_PIXEL_AREA - (((aabb->end.y - line->end.y) * (line->start.x - aabb->start.x)) >> 1);
            }
        } else if ((line->start.y == aabb->start.y) || (line->end.y == aabb->start.y)) {
            if (line->start.y == aabb->start.y) {
                up_area = ((aabb->end.x - line->start.x) * (line->end.y - aabb->start.y)) >> 1;
            } else {
                up_area = ((aabb->end.x - line->end.x) * (line->start.y - aabb->start.y)) >> 1;
            }
        }
    } else { /* 斜率小于0 */
        if ((aabb_h - 1) == IPGUI_ABS(dy)) {
            up_area = ((line->start.x + line->end.x - (aabb->start.x << 1)) * aabb_h) >> 1;
        } else if ((aabb_w - 1) == IPGUI_ABS(dx)) {
            up_area = ((line->start.y + line->end.y - (aabb->start.y << 1)) * aabb_w) >> 1;
        } else if ((line->start.x == aabb->start.x) || (line->end.x == aabb->start.x)) {
            if (line->start.x == aabb->start.x) {
                up_area = ((line->start.y - aabb->start.y) * (line->end.x - aabb->start.x)) >> 1;
            } else {
                up_area = ((line->end.y - aabb->start.y) * (line->start.x - aabb->start.x)) >> 1;
            }
        } else if ((line->start.y == aabb->end.y) || (line->end.y == aabb->end.y)) {
            if (line->start.y == aabb->end.y) {
                up_area = IPGUI_PIXEL_AREA - (((aabb->end.x - line->start.x) * (aabb->end.y- line->end.y)) >> 1);
            } else {
                up_area = IPGUI_PIXEL_AREA - (((aabb->end.x - line->end.x) * (aabb->end.y- line->start.y)) >> 1);
            }
        }
    }

    if (up_down) {/* 计算直线上方的AABB面积 */
        return up_area;
    } else {/* 计算直线下方的AABB面积 */
        return IPGUI_PIXEL_AREA - up_area;
    }
}

/* modify from ipgui_draw_scanline date 20250814 */
__IPGUI_STATIC__ void ipgui_scanline_ras(ipgui_coord_t scan_y, 
                                            ipgui_scoord_t x1, ipgui_scoord_t x2, 
                                            ipgui_scoord_t x3, ipgui_scoord_t x4,
                                            ipgui_triangle_ras_attr_t * attr, ipgui_aabb_t * clip,
                                            ipgui_tile_t * tile)

/* 线(x1,scan_y+1),(x3,scan_y)必须在左边,线(x2,scan_y+1),(x4,scan_y)必须在右边 
 * 即必须满足 x1 <= x2, x3 <= x4
 * x1 x2 x3 x4分布位置如下：
 */
/*     x3----------------------------x4    <-------------------scan_y
        /                            /
        /                           /
        /                          /
        /                         /
        x1-----------------------x2        <-------------------scan_y + 1
*/
{
    ipgui_line_t linex1x3;
    ipgui_line_t linex2x4;
    ipgui_aabb_t aabb;
    ipgui_line_t clip_line;
    unsigned char alpha;

    /* x1_down x2_up x3_down x4_up是连续方块模型的左右边界，不是像素点模型 */
    int x_left = IPGUI_MIN2(ipgui_scoord_down(x1), ipgui_scoord_down(x3));
    int x_right = IPGUI_MAX2(ipgui_scoord_up(x2), ipgui_scoord_up(x4));

    int x_left_diff = (x1 - x_left);
    x_left_diff = (x_left_diff > (x3 - x_left)) ? x_left_diff : (x3 - x_left);
    int x_right_diff = (x_right - x2);
    x_right_diff = (x_right_diff > (x_right - x4)) ? x_right_diff : (x_right - x4);
    x_right_diff = ipgui_scoord_up(x_right_diff);
    x_right_diff = x_right - x_right_diff;

    /* 将x_left和x_right裁剪 */
    if ((x_left >= (clip->end.x << IPGUI_PIXEL_BITS) || x_right <= (clip->start.x << IPGUI_PIXEL_BITS))) 
        return;
    if (x_left < (clip->start.x << IPGUI_PIXEL_BITS))
        x_left = clip->start.x << IPGUI_PIXEL_BITS;
    if (x_right > (clip->end.x << IPGUI_PIXEL_BITS))
        x_right = clip->end.x << IPGUI_PIXEL_BITS;

    int dx1, dx2;
    gen_axis_distance(x1, x3, &dx1);
    gen_axis_distance(x2, x4, &dx2);

    aabb.start.y = 0;
    aabb.end.y = IPGUI_PIXEL_PRECI - 1;

    /* 构造线x1x3和x2x4，将线x1-x3 和 x2-x4移动到0,0 */
    gen_axis_distance(x_left, x1, &linex1x3.start.x);
    gen_axis_distance(x_left, x3, &linex1x3.end.x);
    linex1x3.start.y = IPGUI_PIXEL_PRECI - 1;
    linex1x3.end.y = 0;
    
    gen_axis_distance(x_left, x2, &linex2x4.start.x);
    gen_axis_distance(x_left, x4, &linex2x4.end.x);
    linex2x4.start.y = IPGUI_PIXEL_PRECI - 1;
    linex2x4.end.y = 0;

    int trim, cover;//trim + cover = IPGUI_PIXEL_PRECI * IPGUI_PIXEL_PRECI

    for (int i = x_left; i < x_right; i += IPGUI_PIXEL_PRECI)
    {
        aabb.start.x = i - x_left;
        aabb.end.x = aabb.start.x + IPGUI_PIXEL_PRECI - 1;
        cover = IPGUI_PIXEL_AREA;
        trim = 0;

        if (x_left_diff >= aabb.start.x) {/* 先判断有没有交集 */
                if (0 == ipgui_line_clip_cohen(&aabb, &linex1x3, &clip_line)) { /* 有交集再进行裁剪 */
                /* 判断斜率，大于0就减去直线上方的aabb面积
                 * 小于0就减去直线下方aabb面积,垂线就减去直线左边的aabb面积
                 */
                if (!line_slope_exist(&clip_line)) 
                    trim += (clip_line.start.x - aabb.start.x) << IPGUI_PIXEL_BITS;
                else if (dx1 > 0) trim += gen_trim_area_size(&clip_line, &aabb, 1);
                else if (dx1 < 0) trim += gen_trim_area_size(&clip_line, &aabb, 0);
                else if (dx1 == 0) /* error */;
            }
        }

        if (i >= x_right_diff) { /* 先判断有没有交集 */
            if (0 == ipgui_line_clip_cohen(&aabb, &linex2x4, &clip_line)) {
                /* 判断斜率，大于0就减去下面的面积 
                 * 小于0就减去上面的面积，垂线就减去右边面积
                 */
                if (!line_slope_exist(&clip_line)) 
                    trim += (aabb.end.x - clip_line.end.x) << IPGUI_PIXEL_BITS;
                else if (dx2 > 0) trim += gen_trim_area_size(&clip_line, &aabb, 0);
                else if (dx2 < 0) trim += gen_trim_area_size(&clip_line, &aabb, 1);
                else if (dx2 == 0) /* error */;
            }
        }
        cover -= trim;
        if (cover == IPGUI_PIXEL_AREA) {
            cover = 255;
        } else {
            cover = (cover * 255) / IPGUI_PIXEL_AREA;//[0...IPGUI_PIXEL_AREA]--->[0...255]
        }
        alpha = (cover * attr->alpha) >> 8;

        ipgui_coord_t x_idx = i >> IPGUI_PIXEL_BITS;

        ipgui_coord_t ix, iy;
        ix = x_idx - tile->x1;
        iy = scan_y - tile->y1;
        ipgui_color_t * cr;
        /* blend triangle's color */
        cr = ipgui_tile_buf_get(tile, ix, iy);
        ipgui_color_blend(&attr->color, cr, alpha);

    }
}